#include <bits/stdc++.h>

using namespace std;

/**
 * Definition for a binary tree node.
 */
struct TreeNode {
	int val;
	TreeNode* left;
	TreeNode* right;
	TreeNode() :
		val(0) , left(nullptr) , right(nullptr) { }
	TreeNode(int x)
		: val(x) , left(nullptr) , right(nullptr) { }
	TreeNode(int x, TreeNode* left, TreeNode* right)
		: val(x) , left(left) , right(right) { }
};

class Solution {
public:
	vector<vector<int>> zigzagLevelOrder(TreeNode* root)
	{
		vector<vector<int>> res; deque<int> layer;
		if (!root) return res;

		queue<TreeNode*> aux { { root } };
		auto last = root; bool odd = true;
		while (!aux.empty()) {
			auto p = aux.front(); aux.pop();
			if (odd) layer.emplace_back(p->val);
			else layer.emplace_front(p->val);

			if (p->left) aux.emplace(p->left);
			if (p->right) aux.emplace(p->right);

			if (p == last) {
				res.emplace_back(layer.begin(), layer.end());
				layer.clear(); odd = !odd;
				last = aux.back();
			}
		}

		return res;
	}

private:
};

int main()
{
	Solution solution;
	return 0;
}
